Graphs

Friday, June 05, 2015

9:37 AM

<<graphs.pdf>>

Inserted from: <file://\\psf\Dropbox\Schoolworks\Waterloo Terms\4B\CS431 Algo\graphs.pdf>

$Machine generated alternative text: e!’flrenr Singia Lauros Shmtast Pach Shortest Paths in a DAC If G is a DAG. we perform a topological ordering of the vertices. Suppose the resulting ordering is v. ,. Then we find all the shortest paths in G with source vi. Note: This algorithm is correct even if there are negative-weight edges. Algorithm: DAC Shortest paths(G. u’. vi) for j — 1 to n do 5u] 4— X jr[vJ t— undefined D[vi] 4— () for j *— 1 to n — 1 for all t” E Ãdj[v’ d (if D[vJ + w(vj,v’) < D{v’] do then ¡D[v’:4—Dvi)+u’(viv’) t 1*14—vi return (D, n) DtStinsan (SCS) I— Wnse. 2015 160/lU AH-Pairs Lnsetczt Paths AIl-l-’airs Shortest Paths Problem All-Pairs Shortest Paths Instance: A dfrected graph G = (V E, ana a weignt matrix W, where W[i. j] denotes the weight of edge ¿j, lõr all ¿J E V-, j Find: For all pairs of vertices u. t’ E V, u t’, a directed path P from u to u such that w(P) = TVi.j] hEP is minimized. _____________ We allow edges to have negative weights. but we assume there are no negative-weight directed cycles in G. DL Sth.an (SŒ) Wbitar. 2015 161 1 164$

$Machine generated alternative text: I All-Pairs Sis6czs Paths 4— 1 to n £— oc for k ÷— 1 to n do £ 4— min{É. Lrn_j [1. k] ± w{k. j] } L,4i.j] 4— £ (or j .— 1 to n do do Lm[i.j] 4— £ First Solution Algorithm: S: L W for in 4— 2 to n — 1 for j i— 1 to n for j do do{ do return (La_1) second Solution All-Pairs £nsetczs Paths Algorithm: FasterAÍlPairs5hortestPath(W) L1 W while in < n — 1 (for j .— 1 to n Wbissr. 2015 162 / 164 Et— oc for k 4— 1 to n do Li— rnin{LLm,Lk] ±Lm2[k.j]) do 1m 4— 2m return (Lin) Dt SUman (SCS) Wb,sa. 2015 16] 164$

Machine generated alternative text: All-Pairs S*s.tt Paths
Third Solution
Algorithm: Floyd Warshall(W)
for Tfl 4— 1 to TI
(for j t— 1 to n
do (forj*—ltondo
do Vm[jtil t— min{D j[i.jj.Drn 1[i.m’ —D, i:m,i]}
return (Da)
Wflssr. 2015 164 / 164